package letcode.problem.dynamicProgra;

import java.util.Arrays;

/**
 * https://leetcode.cn/problems/delete-and-earn/description/?envType=study-plan-v2&envId=dynamic-programming
 * */
public class DeleteEarn {
    /**
     * 给你一个整数数组 nums ，你可以对它进行一些操作。
     *
     * 每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。
     *
     * 开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。
     *
     *
     * */
    public static int deleteAndEarn(int[] nums) {
        int maxLen = Arrays.stream(nums).max().orElse(0);
        int[] sums = new int[maxLen + 1];
        for (int num : nums) {
            sums[num] += num;
        }
        return rob(sums);
    }

    public static int rob(int[] sums) {
        int len = sums.length;
        if (len == 1) {
            return sums[0];
        }
        int first = sums[0];
        int second = Math.max(sums[0], sums[1]);
        for (int i = 2; i < len; i++) {
            int third = Math.max(second, first + sums[i]);
            first = second;
            second = third;
        }
        return second;
    }

    public static void main(String[] args) {
        System.out.println(
                deleteAndEarn(new int[]{3, 4, 2})
        );
    }
}
